package com.togo.algorithm.medium.array;

/**
 * 
 * <p>
 * Class : com.togo.algorithm.medium.array.SortColors75
 * <p>
 * Descdription: 给定一个包含红色、白色和蓝色，一共 n
 * 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * 
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * 
 * 注意: 不能使用代码库中的排序函数来解决这道题。
 * 
 * 示例:
 * 
 * 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
 * 
 * 进阶：
 * 
 * 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 *
 * 
 * 
 * @author taiyn
 * @version 1.0.0
 *          <p>
 *          --------------------------------------------------------------<br>
 *          修改履历：<br>
 *          <li>2019年4月17日，taiyn，创建文件；<br>
 *          --------------------------------------------------------------<br>
 *          </p>
 */
public class SortColors75 {

	/**
	 * 
	 * <p>
	 * Method ：sortColors
	 * <p>
	 * Description
	 * :其实就是数字的排序，开始写了一个快速排序实现。后面看了别人的代码，可以针对这个问题做一些代码优化，代码少了很多，但是空间和时间没什么变化；
	 * 思路：1、声明两个指针red和blue分别指向红色和蓝色 2、遍历数组，将等于红色的和red交换，蓝色的和blue交换 3、遍历结束后，白色的则排好序了
	 *
	 * @param nums
	 * @author taiyn
	 *         <p>
	 *         --------------------------------------------------------------<br>
	 *         修改履历：<br>
	 *         <li>2019年4月17日，taiyn，创建方法；<br>
	 *         --------------------------------------------------------------<br>
	 *         </p>
	 */
	public void sortColors(int[] nums) {

		// 红色指向头
		int red = 0;
		// 蓝色指向尾部
		int blue = nums.length - 1;

		// 终止条件是遍历指针和蓝色指针相遇，蓝色指针后面的都是已经排好序的蓝色，所以不用再遍历
		for (int i = 0; i < blue + 1; i++) {

			if (nums[i] == 0) {// 红色

				// 和红色指针交换，并红色指针后移，遍历指针后移
				swap(i++, red++, nums);
			} else if (nums[i] == 2) {// 蓝色

				// 和蓝色指针交换，蓝色指针前移，没有移动遍历指针，这是因为交换后的元素还没有遍历
				swap(i, blue--, nums);
			} else { // 白色，则指针后移
				i++;
			}
		}
	}

	private void swap(int i, int j, int[] nums) {

		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
}
